from typing import List


class Solution:
    def countCornerRectangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        ans = 0

        for i1 in range(m):
            for i2 in range(i1 + 1, m):
                count = 0
                for j in range(n):
                    if grid[i1][j] == 1 and grid[i2][j] == 1:
                        count += 1
                ans += (1 + count - 1) * (count - 1) // 2

        return ans


if __name__ == "__main__":
    # 1
    print(Solution().countCornerRectangles(grid=
                                           [[1, 0, 0, 1, 0],
                                            [0, 0, 1, 0, 1],
                                            [0, 0, 0, 1, 0],
                                            [1, 0, 1, 0, 1]]))

    # 9
    print(Solution().countCornerRectangles(grid=
                                           [[1, 1, 1],
                                            [1, 1, 1],
                                            [1, 1, 1]]))

    # 0
    print(Solution().countCornerRectangles(grid=
                                           [[1, 1, 1, 1]]))
